package graph;

import java.util.*;

/**
 * @BelongsProject: leetcode
 * @BelongsPackage: graph
 * @author: 肖
 * @date: 2022/1/30 10:03
 * @Description: K算法 从边开始 判断是否有环
 * @since JDK 11
 */

public class Kruskal {
    public static class MySets{
//      点对应的集合
        public HashMap<NodeG, List<NodeG>> setMap;

        public MySets(List<NodeG> nodes) {
            for(NodeG cur : nodes){
                List<NodeG> set = new ArrayList<NodeG>();
                set.add(cur);
                setMap.put(cur,set);
            }
        }

        public boolean isSameSet(NodeG from, NodeG to) {
            List<NodeG> fromSet = setMap.get(from);
            List<NodeG> toSet = setMap.get(to);
            return fromSet==toSet;
        }

        public void union(NodeG from, NodeG to){
            List<NodeG> fromSet = setMap.get(from);
            List<NodeG> toSet = setMap.get(to);
            for(NodeG toNode : toSet){
                fromSet.add(toNode);
                setMap.put(toNode,fromSet);
            }
        }

    }

//    public static Set<Edge> kruskalMST (Graph graph){
////       并查集结构
//        UnionFind unionFind = new UnionFind();
//        unionFind.makeSets(Graph.nodes.values());
//        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>((o1,o2)->{
//            return o1.weight-o2.weight;
//        });
//        for (Edge edge : graph.edges){
//            priorityQueue.add(edge);
//        }
//        Set<Edge> result = new HashSet<>();
//        while (!priorityQueue.isEmpty()){
//            Edge edge = priorityQueue.poll();
//            if(!unionFind.isSameSet(edge.from,edge.set)){
//                result.add(edge);
//                unionFind.union(edge.from,edge.set);
//            }
//        }
//        return result ;
//    }
}
